package algorithms.que13;

/**
 * @功能
 * @创建时间 2020/8/1
 */
public class StackPro<Item extends Comparable<Item> >{

    /**
     * @param args
     */
    private Node first;
    private int N;
    private class Node{
        Item item;
        Node next;
    }
    public boolean isEmpty(){
        return first == null;
    }
    public int size(){
        return N;
    }
    private boolean check(Item item){
        if(N<2) return true;
        Node cur = first;
        Item min1, min2;
        if(cur.item.compareTo(cur.next.item)<0){
            min1 = cur.item;
            min2 = cur.next.item;
        }
        else {
            min1 = cur.next.item;
            min2 = cur.item;
        }

        for(cur = cur.next.next;cur!=null; cur = cur.next){
            if(cur.item.compareTo(min2)<0){
                if(cur.item.compareTo(min1)>0)
                    min2 = cur.item;
                else {
                    min2 = min1;
                    min1 = cur.item;
                }
            }
        }
        return min2.compareTo(item)<=0;
    }
    public void push(Item item){
        if(check(item)==false) return;
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }
    public Item peek(){
        if(N==0) return null;
        return first.item;
    }
    public Item pop(){
        Item item = first.item;
        first = first.next;
        N -- ;
        return item;
    }

}

